package main

import (
	"fmt"
)

type CircleLink struct {
	id   int         //编号
	data interface{} // 数据
	Prev *CircleLink // 上一个
	Next *CircleLink //
}

func InitHeadNode(data interface{}) *CircleLink {
	return &CircleLink{0, data, nil, nil}
}

func (clink *CircleLink) IsHeadEmpty() bool {
	return clink.Prev == nil && clink.Next == nil
}

// 是否为空
func (clink *CircleLink) IsEmpty() bool {
	return clink.data == nil && clink.Prev == nil && clink.Next == nil
}

func (clink *CircleLink) AddNode(newNode *CircleLink) {
	if clink.IsHeadEmpty() { // 只有一个节点  互为前后
		clink.Prev = newNode
		clink.Next = newNode

		newNode.Prev = clink
		newNode.Next = clink

		return
	}
	curnode := clink
	flag := false

	for {
		if curnode == clink.Prev {
			break //已经是最后一个节点，退出
		} else if curnode.Next.id > newNode.id {
			flag = true //标志下数据应该插入到前列
			break
		} else if newNode.id == clink.id {
			fmt.Printf("数据已经存在\n")
			break
		}
		curnode = curnode.Next
	}

	if flag {
		//最后一个节点，前面插入
		newNode.Next = curnode.Next
		newNode.Prev = curnode

		curnode.Next.Prev = newNode
		curnode.Next = newNode

	} else {
		//最后一个后面插入
		newNode.Next = curnode.Next
		newNode.Prev = curnode

		curnode.Next = newNode
		clink.Prev = newNode

	}

}

// 显示数据
func (clink *CircleLink) ShowAll() {
	if clink.IsEmpty() {
		fmt.Printf("空链表无法显示\n")
		return
	}

	if clink.IsHeadEmpty() {
		fmt.Println(clink.id, clink.data, clink.Prev, clink.Next)
		return
	}

	curnode := clink
	for {
		fmt.Println(clink.id, clink.data)
		if curnode == clink.Next {
			break
		}
		clink = clink.Next
	}

}

//查找某个节点不存在
func (clink *CircleLink) FindNodeById(id int) (*CircleLink, bool) {
	if clink.IsHeadEmpty() && clink.id == id {
		return clink, true
	} else if clink.IsHeadEmpty() && clink.id != id {
		return &CircleLink{}, false
	}

	curnode := clink
	flag := false

	for {
		if curnode.id == id {
			flag = true
			break
		}
		if curnode == clink.Prev {
			break
		}
		curnode = curnode.Next
	}

	if !flag {
		return &CircleLink{}, false
	}

	return curnode, flag

}

//删除某个节点
func (clink *CircleLink) Deletenodebyid(id int) bool {
	if clink.IsEmpty() {
		fmt.Println("列表为空")
		return false
	}

	node, isok := clink.FindNodeById(id) //搜索判断是否存在

	if isok {
		//删除第一个节点
		if node == clink {
			// 只有一个节点
			if clink.IsHeadEmpty() {
				clink.id = 0
				clink.data = nil
				clink.Prev = nil
				clink.Next = nil
				return true
			}
			//只有两个节点
			if clink.Next.Next == clink {
				nextnode := clink.Next
				clink.id = nextnode.id
				clink.data = nextnode.data
				clink.Prev = nil
				clink.Next = nil

				return true

			}

			//双环链表，始终保留第一个节点
			//移动下一个节点作为头节点

			nextNodetmp := clink.Next
			clink.id = nextNodetmp.id
			clink.data = nextNodetmp.data
			clink.Next = nextNodetmp.Next
			clink.Next.Prev = clink

			return true
		}

		//删除最后一个节点
		if node == clink.GetLastNode() {

			if node.Prev == clink && node.Next == clink {
				clink.Next = nil
				clink.Prev = nil
				return true
			}

			clink.Prev = node.Prev
			node.Prev.Next = clink
			return true
		}

		node.Prev.Next = node.Next
		node.Next.Prev = node.Prev
		return true
	} else {
		fmt.Printf("数据找不到所以无法删除\n")
	}

	return isok
}

// 获取最后一个
func (clink *CircleLink) GetLastNode() *CircleLink {
	curnode := clink
	if !clink.IsHeadEmpty() {
		for {
			if curnode.Next == clink { //循环到了最后
				break
			}
			curnode = curnode.Next
		}
	}
	return curnode
}

// 修改节点的值
func (clink *CircleLink) ChangeNode(id int, data interface{}) bool {
	node, isok := clink.FindNodeById(id)
	if isok {
		node.data = data
	} else {
		fmt.Println("该节点不存在")
	}
	return isok

}

func main() {
	linknode := InitHeadNode("a")
	linknode.ShowAll()
	fmt.Println("---------------")

	node1 := &CircleLink{3, "b", nil, nil}

	linknode.AddNode(node1)
	//linknode.ShowAll()

	node2 := &CircleLink{2, "c", nil, nil}

	linknode.AddNode(node2)
	//linknode.ShowAll()

	node3 := &CircleLink{5, "d", nil, nil}

	linknode.AddNode(node3)
	//linknode.ShowAll()

	node4 := &CircleLink{4, "e", nil, nil}

	linknode.AddNode(node4)
	// linknode.ShowAll()

	// linknode.Deletenodebyid(5)
	linknode.ShowAll()

	linknode.ChangeNode(3, "aaa")
	linknode.ShowAll()

}
